#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

//409.最长回文串
int longestPalindrome(string s){
    //建立哈希表，统计字符的个数
    unordered_map<char, int> hash;
    for(auto ch : s){
        hash[ch]++;
    }

    int ret = 0;
    for(auto& [ch,count] : hash){
        //不管个数是奇数还是偶数，都是先除以2再乘以2
        ret += count / 2 * 2;
    }

    //如果最后回文串的长度小于原字符串的长度，说明存在奇数个的字符，回文串长度再+1
    if(ret<s.size()){
        ret++;
    }
    return ret;
}

//942.增减字符串匹配
vector<int> diStringMatch(string s){
    //贪心策略：遇到'I'选择最小的数，遇到'D'选择最大的数

    int n = s.size();
    int left = 0, right = n;

    vector<int> ret(n + 1);
    for (int i = 0; i < n; i++){
        if(s[i]=='I'){
            ret[i] = left++;
        }
        else{
            ret[i] = right--;
        }
    }
    //最后一个位置用剩下的一个值填充
    ret[n] = left;
    return ret;
}

//455.分发饼干
int findContentChildren(vector<int>& g, vector<int>& s){
    //贪心策略，先将两个数组排序，在能满足当前胃口的情况下选择较小的饼干

    sort(g.begin(),g.end());
    sort(s.begin(), s.end());

    int ret = 0;
    for (int i = 0, j = 0; i < g.size() && j < s.size(); ){
        //如果当前饼干能满足当前胃口值，直接选择当前饼干
        if(s[j]>=g[i]){
            ret++;
            i++;
            j++;
        }
        //否则，跳过当前饼干
        else{
            j++;
        }
    }

    return ret;
}

//553.最优除法
string optimalDivision(vector<int>& nums){
    //先处理个数小于等于2的情况
    if(nums.size()==1){
        return to_string(nums[0]);
    }
    if(nums.size()==2){
        return to_string(nums[0]) + '/' + to_string(nums[1]);
    }

    string ret;
    //只在第一个数后面加上（，最后一个数后面加上）
    for (int i = 0; i < nums.size(); i++){
        ret += to_string(nums[i]);
        if(i==0){
            ret += "/(";
        }
        else if(i==nums.size()-1){
            ret += ')';
        }
        else{
            ret += '/';
        }
    }
    return ret;
}

//45.跳跃游戏2
int jump(vector<int>& nums){
    //左指针表示当前位置可以跳的最左位置，也就是跳的最小的步数位置
    //右指针和maxpos指针表示当前位置可以跳的最右位置，也就是跳的最大的步数位置
    int left = 0, right = 0, maxpos = 0;
    int n = nums.size();
    int ret = 0;

    //循环条件，当出现左指针大于右指针，结束，表示不能跳到最终位置
    while(left<=right){
        //如果maxpos指针的位置大于等于数组的长度，结束
        if(maxpos>=n-1){
            return ret;
        }

        //从当前左指针位置遍历到右指针位置，更新下一次可以跳到的最右位置
        for (int i = left; i <= right; i++){
            maxpos = max(maxpos, nums[i] + i);
        }

        //左指针更新为当前右指针的下一个，表示最少跳一步
        left=right+1;
        //右指针更新为maxpos指向的位置，表示最多跳的步数
        right = maxpos;

        ret++;
    }

    return -1;
}

//跳跃游戏
bool canJump(vector<int>& nums){
    //和跳跃游戏2相同，只是返回结果不同
    int left = 0, right = 0, maxpos = 0;
    int n=nums.size();

    while(left<=right){
        if(maxpos>=n-1){
            return true;
        }

        for (int i = left; i <= right; i++){
            maxpos = max(maxpos, nums[i] + i);
        }

        left=right+1;
        right = maxpos;
    }

    return false;
}

int main(){

    return 0;
}